//
// Created by vista on 2017/12/11.
//

#ifndef P_P15_H
#define P_P15_H

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <set>
using namespace std;

class Solution {
public:


    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;

        if(nums.size() < 3)
            return result;

        sort(nums.begin(),nums.end());

        int l = 0, r = static_cast<int>(nums.size() - 1);

        while (nums[l] <= 0 && r-l >= 2) {
            int left = nums[l];
            do {
                int right = nums[r];
                int mid = 0 - left - right;
                if(mid > right){
                    break;
                }
                auto ptr = binary_search(nums.begin() + l + 1, nums.begin() + r, mid);
                if (ptr) {
                    vector<int> tmp;
                    tmp.push_back(left);
                    tmp.push_back(mid);
                    tmp.push_back(right);

                    result.emplace_back(tmp);
                }

                do{
                    --r;
                }while (nums[r] == right);

            } while (r - l >= 2 && nums[r] >= 0);
            do{
                ++l;
            }while (nums[l] == left);
            r = static_cast<int>(nums.size() - 1);
        }

        return result;
    }
};
#endif //P_P15_H
